package primary.primary0;

import java.util.Arrays;

public class S0279完全平方数 {


    /**
     * 数学法
     */
    public int numSquares3(int n) {

        return - 1;
    }


    /**
     * 28, 37
     * 用动态规划，从1算到n即可。
     */
    public int numSquares2(int n) {
        int[] numList = new int[n + 1];
        // 初值怎么改? 注意这里不能闭着眼睛塞Integer.MAX_VALUE, 要不然 + 1的时候容易直接溢出变成负数，整体就崩了。
        Arrays.fill(numList, 10000);
        numList[0] = 0;
        for(int i = 0; i <= n; i++){
            for(int j = 1; j * j <= i; j++){
                numList[i] = Math.min(numList[i], numList[i - j * j] + 1);
            }
        }
        return numList[n];
    }



    /**
     * 51， 99
     * 看起来是完全背包问题
     * 不清楚怎么用背包的思想去做，先试一下深度遍历吧，层序遍历感觉时间可能笔深度遍历多
     * 注意Math.pow只能用到double头上
     */
    public int numSquares(int n) {
        for(int i = 0; i <= 101; i++){
            if(i * i > n){
                maxSNum = i - 1;
                break;
            }
        }
        dfsSearch(n, maxSNum, 0);
        return minDepth;
    }

    /**
     * 平方比n小的最大的完全平方数
     */
    private static int maxSNum = 0;

    int minDepth = 10000;

    /* 可不能找到一个就停，后面的不走完不知道有没有更短的 */
    // boolean stopFlag = false;

    private void dfsSearch(int n, int curLimitSNum, int curDepth){
        // 这里的终止非常重要，dfs带上终止一般能通过，不带基本都超时
        if(curDepth >= minDepth){
            return ;
        }
        if(n < 0){
            return;
        }
        // 当前减成0了
        if(n == 0){
            minDepth = Math.min(minDepth, curDepth);
            return;
        }
        for(int i = curLimitSNum; i > 0; i --){
            dfsSearch(n - i*i, i, curDepth + 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(new S0279完全平方数().numSquares(13));
    }
}
